
<!DOCTYPE HTML>
<html lang="zh-hans" >
    <head>
        <meta charset="UTF-8">
        <meta content="text/html; charset=utf-8" http-equiv="Content-Type">
        <title>主定理证明 · Algorithm Notes</title>
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="description" content="">
        <meta name="generator" content="GitBook 3.2.3">
        <meta name="author" content="Avanti">
        
        
    
    
    <link rel="stylesheet" href="../gitbook/style.css">

    
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-splitter/splitter.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-disqus/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-donate/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-search-plus/search.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-advanced-emoji/emoji-website.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-emphasize/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-mermaid-gb3/mermaid/mermaid.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-tbfed-pagefooter/footer.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-anchors/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-terminal/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-highlight/website.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-fontsettings/website.css">
                
            
        

    

    
        
        <link rel="stylesheet" href="../styles/website.css">
        
    


    

        
    
    
    
    
    
    <meta name="HandheldFriendly" content="true"/>
    <meta name="viewport" content="width=device-width, initial-scale=1, user-scalable=no">
    <meta name="apple-mobile-web-app-capable" content="yes">
    <meta name="apple-mobile-web-app-status-bar-style" content="black">
    <link rel="apple-touch-icon-precomposed" sizes="152x152" href="../gitbook/images/apple-touch-icon-precomposed-152.png">
    <link rel="shortcut icon" href="../gitbook/images/favicon.ico" type="image/x-icon">

    
    
    <link rel="prev" href="Strassen.html" />
    

    
    <link rel="stylesheet" href="../gitbook/gitbook-plugin-chart/c3/c3.min.css">
    <script src="../gitbook/gitbook-plugin-chart/c3/d3.min.js"></script>
    <script src="../gitbook/gitbook-plugin-chart/c3/c3.min.js"></script>
    

    <script src="../gitbook/gitbook-plugin-graph/d3.min.js"></script>
    <script src="../gitbook/gitbook-plugin-graph/function-plot.js"></script>    

    <style>
    @media only screen and (max-width: 640px) {
        .book-header .hidden-mobile {
            display: none;
        }
    }
    </style>
    <script>
        window["gitbook-plugin-github-buttons"] = {};
    </script>

    </head>
    <body>
        
<div class="book">
    <div class="book-summary">
        
            
<div id="book-search-input" role="search">
    <input type="text" placeholder="输入并搜索" />
</div>

            
                <nav role="navigation">
                


<ul class="summary">
    
    

    

    
        
        
    
        <li class="chapter " data-level="1.1" data-path="../">
            
                <a href="../">
            
                    
                    算法导论
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2" data-path="Strassen.html">
            
                <a href="Strassen.html">
            
                    
                    矩阵乘法加速
            
                </a>
            

            
        </li>
    
        <li class="chapter active" data-level="1.3" data-path="master-theorem.html">
            
                <a href="master-theorem.html">
            
                    
                    主定理证明
            
                </a>
            

            
        </li>
    

    

    <li class="divider"></li>

    <li>
        <a href="https://www.gitbook.com" target="blank" class="gitbook-link">
            本书使用 GitBook 发布
        </a>
    </li>
</ul>


                </nav>
            
        
    </div>

    <div class="book-body">
        
            <div class="body-inner">
                
                    

<div class="book-header" role="navigation">
    

    <!-- Title -->
    <h1>
        <i class="fa fa-circle-o-notch fa-spin"></i>
        <a href=".." >主定理证明</a>
    </h1>
</div>




                    <div class="page-wrapper" tabindex="-1" role="main">
                        <div class="page-inner">
                            
<div class="search-plus" id="book-search-results">
    <div class="search-noresults">
    
                                <section class="normal markdown-section">
                                
                                <p><strong>&#x4E3B;&#x5B9A;&#x7406;</strong>&#xFF1A;&#x4EE4;<script type="math/tex; ">a \ge 1</script>&#x548C;<script type="math/tex; ">b > 1</script>&#x662F;&#x5E38;&#x6570;&#xFF0C;<script type="math/tex; ">f(n)</script>&#x662F;&#x4E00;&#x4E2A;&#x51FD;&#x6570;&#xFF0C;<script type="math/tex; ">T(n)</script>&#x662F;&#x5B9A;&#x4E49;&#x5728;<strong>&#x975E;&#x8D1F;&#x6574;&#x6570;</strong>&#x4E0A;&#x7684;&#x9012;&#x5F52;&#x5F0F;&#xFF1A;
\begin{align*}
    T(n) = a \cdot \left( \frac{n}{b} \right) + f(n)
\end{align*}
&#x5176;&#x4E2D;&#x6211;&#x4EEC;&#x5C06;<script type="math/tex; ">n/b</script>&#x89E3;&#x91CA;&#x4E3A;<script type="math/tex; ">\lfloor n/b \rfloor</script>&#x6216;<script type="math/tex; ">\lceil n/b \rceil</script>&#xFF0C;&#x90A3;&#x4E48;<script type="math/tex; ">T(n)</script>&#x6709;&#x5982;&#x4E0B;&#x6E10;&#x8FDB;&#x754C;&#xFF1A;</p>
<ol>
<li>&#x82E5;&#x5BF9;&#x67D0;&#x4E2A;&#x5E38;&#x6570;<script type="math/tex; ">\varepsilon > 0</script>&#x6709;<script type="math/tex; ">f(n) = O(n^{\log_b a - \varepsilon})</script>&#xFF0C;&#x5219;<script type="math/tex; ">T(n) = \Theta (n^{\log_b a})</script>&#x3002;</li>
<li>&#x82E5;<script type="math/tex; ">f(n) = \Theta (n^{\log_b a})</script>&#xFF0C;&#x5219;<script type="math/tex; ">T(n) = \Theta (n^{\log_b a} \lg n)</script>&#x3002;</li>
<li>&#x82E5;&#x5BF9;&#x67D0;&#x4E2A;&#x5E38;&#x6570;<script type="math/tex; ">\varepsilon > 0</script>&#x6709;<script type="math/tex; ">f(n) = \Omega(n^{\log_b a + \varepsilon})</script>&#xFF0C;&#x4E14;&#x5BF9;&#x67D0;&#x4E2A;&#x5E38;&#x6570;<script type="math/tex; ">c<1</script>&#x548C;&#x6240;&#x6709;&#x8DB3;&#x591F;&#x5927;&#x7684;<script type="math/tex; ">n</script>&#x6709;<script type="math/tex; ">a f(n/b) \le c f(n)</script>&#xFF0C;&#x5219;<script type="math/tex; ">T(n) = \Theta (f(n))</script>&#x3002;</li>
</ol>
<p><strong>&#x8BC1;&#x660E;</strong>&#xFF1A;&#x82E5;<script type="math/tex; ">n</script>&#x662F;<script type="math/tex; ">b</script>&#x7684;&#x6574;&#x6570;&#x5E42;&#x6B21;&#xFF0C;&#x4E0D;&#x59A8;&#x8BBE;<script type="math/tex; ">n = b^k</script>&#xFF0C;&#x6B64;&#x65F6;<script type="math/tex; ">n/b</script>&#x6700;&#x540E;&#x6B63;&#x597D;&#x4F1A;&#x9012;&#x5F52;&#x6210;<script type="math/tex; ">1</script>&#xFF0C;&#x5373;
\begin{align*}
    T \left( \frac{n}{b^0} \right)     &amp; = a \cdot T \left( \frac{n}{b^1} \right) + f \left( \frac{n}{b^0} \right)     \\
    T \left( \frac{n}{b^1} \right)     &amp; = a \cdot T \left( \frac{n}{b^2} \right) + f \left( \frac{n}{b^1} \right)     \\
                                       &amp; \vdots                                                                        \\
    T \left( \frac{n}{b^{k-1}} \right) &amp; = a \cdot T \left( \frac{n}{b^k} \right) + f \left( \frac{n}{b^{k-1}} \right)
\end{align*}
&#x6CE8;&#x610F;&#x4E0A;&#x9762;&#x5171;&#x6709;<script type="math/tex; ">k</script>&#x4E2A;&#x9012;&#x63A8;&#x5F0F;&#xFF0C;&#x53C8;<script type="math/tex; ">a^k = (b^{\log_b a})^k = (b^k)^{\log_b a} = n^{\log_b a}</script>&#x3001;<script type="math/tex; ">n = b^k</script>&#xFF0C;&#x4E8E;&#x662F;
\begin{align*}
    T(n) = a^k \cdot T \left( \frac{n}{b^k} \right) + f \left( \frac{n}{b^0} \right) + a f \left( \frac{n}{b^1} \right) + \cdots + a^{k-1} f \left( \frac{n}{b^{k-1}} \right) = n^{\log_b a} \cdot T(1) + \sum_{i=0}^{k-1} a^i f \left( \frac{n}{b^i} \right)
\end{align*}
&#x663E;&#x7136;&#x524D;&#x4E00;&#x9879;<script type="math/tex; ">n^{\log_b a} \cdot T(1) = \Theta(n^{\log_b a})</script>&#xFF0C;&#x6545;&#x5173;&#x952E;&#x5C31;&#x662F;&#x540E;&#x9762;&#x6C42;&#x548C;&#x8FD9;&#x4E00;&#x9879;&#xFF0C;&#x4E0B;&#x9762;&#x5206;&#x60C5;&#x51B5;&#x8BA8;&#x8BBA;&#xFF1A;</p>
<ol>
<li><p>&#x7531;<script type="math/tex; ">f(n) = O(n^{\log_b a - \varepsilon})</script>&#x53EF;&#x77E5;
\begin{align*}
 a^i f \left( \frac{n}{b^i} \right) = a^i O \left( \left( \frac{n}{b^i} \right)^{\log_b a - \varepsilon} \right) = a^i O \left( \frac{n^{\log_b a - \varepsilon}}{a^i b^{-\varepsilon i}} \right) = O(n^{\log_b a - \varepsilon}) b^{\varepsilon i}
\end{align*}
&#x6545;
\begin{align*}
 g(n) = \sum_{i=0}^{k-1} f \left( \frac{n}{b^i} \right) = O(n^{\log_b a - \varepsilon}) \sum_{i=0}^{k-1} b^{\varepsilon i} = O(n^{\log_b a - \varepsilon}) \frac{1 - b^{k \varepsilon}}{1 - b^\varepsilon} = O(n^{\log_b a - \varepsilon}) \frac{n^\varepsilon - 1}{b^\varepsilon - 1} = O(n^{\log_b a})
\end{align*}
&#x4ECE;&#x800C;<script type="math/tex; ">T(n) = \Theta(n^{\log_b a}) + O(n^{\log_b a}) = \Theta(n^{\log_b a})</script>&#xFF0C;&#x5373;&#x6B64;&#x65F6;<script type="math/tex; ">T(n)</script>&#x7684;&#x590D;&#x6742;&#x5EA6;&#x7531;&#x524D;&#x4E00;&#x9879;&#x51B3;&#x5B9A;&#x3002;</p>
</li>
<li><p>&#x7531;<script type="math/tex; ">f(n) = \Theta (n^{\log_b a})</script>&#x53EF;&#x77E5;
\begin{align*}
 a^i f \left( \frac{n}{b^i} \right) = a^i \Theta \left( \left( \frac{n}{b^i} \right)^{\log_b a} \right) = a^i \Theta \left( \frac{n^{\log_b a}}{a^i} \right) = \Theta(n^{\log_b a})
\end{align*}
&#x4E8E;&#x662F;
\begin{align*}
 g(n) = \sum_{i=0}^{k-1} a^i f \left( \frac{n}{b^i} \right) = \sum_{i=0}^{k-1} \Theta(n^{\log_b a}) = \Theta(n^{\log_b a}) \log_b n = \Theta(n^{\log_b a} \lg n)
\end{align*}
&#x4ECE;&#x800C;<script type="math/tex; ">T(n) = \Theta(n^{\log_b a}) + \Theta(n^{\log_b a} \lg n) = \Theta(n^{\log_b a} \lg n)</script>&#xFF0C;&#x5373;&#x6B64;&#x65F6;<script type="math/tex; ">T(n)</script>&#x7684;&#x590D;&#x6742;&#x5EA6;&#x7531;&#x6C42;&#x548C;&#x8FD9;&#x4E00;&#x9879;&#x51B3;&#x5B9A;&#x3002;</p>
</li>
<li><p>&#x7531;&#x6761;&#x4EF6;&#x77E5;&#x5B58;&#x5728;<script type="math/tex; ">j</script>&#x4F7F;&#x5F97;&#x5F53;<script type="math/tex; ">n' \ge b^{k-j+1} = n / b^{j-1}</script>&#x65F6;&#x9012;&#x63A8;&#x5F0F;<script type="math/tex; ">a f(n'/b) \le c f(n')</script>&#x6052;&#x6210;&#x7ACB;&#xFF0C;&#x4E8E;&#x662F;
\begin{align*}
 a^j f \left( \frac{n}{b^j} \right) \le a^{j-1} c f \left( \frac{n}{b^{j-1}} \right) \le \cdots \le a^2 c^{j-2} f \left( \frac{n}{b^2} \right) \le a c^{j-1} f \left( \frac{n}{b} \right) \le c^j f(n)
\end{align*}
&#x4ECE;&#x800C;&#x5BF9;<script type="math/tex; ">\forall i \le j</script>&#x6709;<script type="math/tex; ">a^i f(n/b^i) \le c^{i} f(n)</script>&#xFF0C;&#x4EE3;&#x5165;&#x53EF;&#x5F97;
\begin{align*}
 g(n) &amp; = \sum_{i=0}^{k-1} a^i f \left( \frac{n}{b^i} \right) = \sum_{i=0}^j a^i f \left( \frac{n}{b^i} \right) + \overbrace{a^{j+1} f \left(\frac{n}{b^{j+1}} \right) + \cdots + a^{k-1} f \left(\frac{n}{b^{k-1}} \right)}^{\text{&#x4E0D;&#x6EE1;&#x8DB3;&#x9012;&#x63A8;&#x5F0F;&#x7684;&#x90E8;&#x5206;&#xFF0C;&#x590D;&#x6742;&#x5EA6;&#x4E3A;}O(1)} \\
 &amp; \le \sum_{i=0}^j c^i f(n) + O(1) &lt; f(n) \sum_{i=0}^\infty c^i + O(1) = \frac{f(n)}{1-c} + O(1) = O(f(n))
\end{align*}
&#x53C8;<script type="math/tex; ">f(n)</script>&#x662F;<script type="math/tex; ">g(n)</script>&#x4E2D;&#x7684;&#x4E00;&#x9879;&#x4E14;<script type="math/tex; ">g(n)</script>&#x6240;&#x6709;&#x6C42;&#x548C;&#x9879;&#x975E;&#x8D1F;&#xFF0C;&#x6545;<script type="math/tex; ">g(n) \ge f(n)</script>&#xFF0C;&#x4ECE;&#x800C;
\begin{align*}
 g(n) = \Theta (f(n)) = \Omega(n^{\log_b a + \varepsilon}) &gt; \Theta(n^{\log_b a})
\end{align*}
&#x4E8E;&#x662F;<script type="math/tex; ">T(n) = \Theta(n^{\log_b a}) + g(n) = \Theta (f(n))</script>&#xFF0C;&#x5373;&#x6B64;&#x65F6;<script type="math/tex; ">T(n)</script>&#x7684;&#x590D;&#x6742;&#x5EA6;&#x7531;&#x6C42;&#x548C;&#x8FD9;&#x4E00;&#x9879;&#x51B3;&#x5B9A;&#x3002;</p>
</li>
</ol>
<hr>
<p>&#x3000;&#x3000;&#x82E5;<script type="math/tex; ">n</script>&#x4E0D;&#x662F;<script type="math/tex; ">b</script>&#x7684;&#x6574;&#x6570;&#x5E42;&#x6B21;&#xFF0C;&#x5219;&#x9012;&#x63A8;&#x4E2D;&#x67D0;&#x4E00;&#x8F6E;<script type="math/tex; ">n/b</script>&#x4E0D;&#x4E00;&#x5B9A;&#x4E3A;&#x6574;&#x6570;&#xFF0C;&#x53C8;<script type="math/tex; ">T(n)</script>&#x662F;&#x5B9A;&#x4E49;&#x5728;&#x975E;&#x8D1F;&#x6574;&#x6570;&#x4E0A;&#x7684;&#xFF0C;&#x56E0;&#x6B64;&#x8FD8;&#x9700;&#x591A;&#x505A;&#x4E00;&#x6B65;&#x53D6;&#x6574;&#xFF0C;&#x6B64;&#x65F6;&#x9012;&#x63A8;&#x5F0F;&#x53EF;&#x5199;&#x6210;
\begin{align*}
    T(n_0) &amp; = a \cdot T(n_1) + f(n_0), \quad n_1 = [n_0/b] \\
    T(n_1) &amp; = a \cdot T(n_2) + f(n_1), \quad n_2 = [n_1/b] \\
    T(n_2) &amp; = a \cdot T(n_3) + f(n_2), \quad n_3 = [n_2/b] \\
    &amp; \vdots
\end{align*}
&#x4E0D;&#x59A8;&#x5148;&#x8003;&#x8651;&#x5411;&#x4E0A;&#x53D6;&#x6574;&#xFF0C;&#x5373;
\begin{align*}
    n_i = \begin{cases}
              n &amp; i = 0 \\ \lceil n_{i-1} / b \rceil &amp; i &gt; 0
          \end{cases}
\end{align*}
&#x6839;&#x636E;<script type="math/tex; ">x \le \lceil x \rceil \le x + 1</script>&#x6613;&#x77E5;
\begin{align*}
    \frac{n}{b}   \le n_1 &amp; \le \frac{n}{b} + 1                                 \\
    \frac{n}{b^2} \le n_2 &amp; \le \frac{n}{b^2} + \frac{1}{b} + 1                 \\
    \frac{n}{b^3} \le n_3 &amp; \le \frac{n}{b^3} + \frac{1}{b^2} + \frac{1}{b} + 1 \\
    \vdots                &amp;
\end{align*}
&#x4E8E;&#x662F;
\begin{align} \label{eq: ni-upper-bound}
    \frac{n}{b^i} \le n_i \le \frac{n}{b^i} + \frac{1}{b^{i-1}} + \cdots + \frac{1}{b} + 1 &lt; \frac{n}{b^i} + \frac{1}{1 - 1/b} = \frac{n}{b^i} + \frac{b}{b-1}
\end{align}
&#x4EE4;<script type="math/tex; ">k = \lfloor \log_b n \rfloor \ge \log_b n - 1</script>&#xFF0C;&#x5373;<script type="math/tex; ">n \le b^{k+1}</script>&#xFF0C;&#x4EE3;&#x5165;&#x5F0F;(\ref{eq: ni-upper-bound})&#x53EF;&#x5F97;
\begin{align*}
    n_k &lt; \frac{n}{b^k} + \frac{b}{b-1} \le \frac{b^{k+1}}{b^k} + \frac{b}{b-1} = b + \frac{b}{b-1} = O(1)
\end{align*}
&#x6545;&#x9012;&#x63A8;&#x5230;&#x7B2C;<script type="math/tex; ">k</script>&#x8F6E;&#xFF0C;&#x5B50;&#x95EE;&#x9898;<script type="math/tex; ">T(n_k)</script>&#x5DF2;&#x7ECF;&#x662F;<script type="math/tex; ">O(1)</script>&#x590D;&#x6742;&#x5EA6;&#x4E86;&#xFF0C;&#x540C;&#x524D;&#x9762;&#x4E00;&#x6837;&#x6709;
\begin{align*}
    T(n) = a^k T(n_k) + f(n_0) + a f(n_1) + \cdots + a^{k-1} f(n_{k-1}) = \Theta(n^{\log_b a}) + \sum_{i=0}^{k-1} a^i f(n_i)
\end{align*}
&#x5173;&#x952E;&#x4F9D;&#x7136;&#x662F;&#x540E;&#x9762;&#x6C42;&#x548C;&#x8FD9;&#x4E00;&#x9879;&#xFF0C;&#x7EE7;&#x7EED;&#x5206;&#x60C5;&#x51B5;&#x8BA8;&#x8BBA;&#xFF1A;</p>
<ol>
<li><p>&#x7531;<script type="math/tex; ">f(n) = O(n^{\log_b a - \varepsilon})</script>&#x53EF;&#x77E5;&#x5B58;&#x5728;&#x6B63;&#x5E38;&#x6570;<script type="math/tex; ">c_i</script>&#x548C;<script type="math/tex; ">n_i</script>&#x4F7F;&#x5F97;&#x5BF9;<script type="math/tex; ">\forall n \ge n_i</script>&#x6709;
\begin{align*}
 a^i f(n_i) &amp; \le a^i c_i n_i^{\log_b a - \varepsilon} &lt; a^i c_i \left( \frac{n}{b^i} + \frac{b}{b-1} \right)^{\log_b a - \varepsilon} = a^i c_i \left( \frac{n}{b^i} \right)^{\log_b a - \varepsilon} \left( 1 + \frac{b^i}{n} \frac{b}{b-1} \right)^{\log_b a - \varepsilon} \\
 &amp; \le a^i c_i n^{\log_b a - \varepsilon} \frac{b^{\varepsilon i}}{a^i} \left( 1 + \frac{b}{b-1} \right)^{\log_b a - \varepsilon} = c_i n^{\log_b a - \varepsilon} b^{\varepsilon i} \left( \frac{2b-1}{b-1} \right)^{\log_b a - \varepsilon}
\end{align*}
&#x4EE4;<script type="math/tex; ">\cbar = \max_i \{c_i\}</script>&#x3001;<script type="math/tex; ">\nbar = \max_i \{n_i\}</script>&#xFF0C;&#x4E8E;&#x662F;&#x5BF9;<script type="math/tex; ">\forall n \ge \nbar</script>&#x6709;
\begin{align*}
 g(n) &amp; = \sum_{i=0}^{k-1} a^i f(n_i) &lt; \sum_{i=0}^{k-1} c_i n^{\log_b a - \varepsilon} b^{\varepsilon i} \left( \frac{2b-1}{b-1} \right)^{\log_b a - \varepsilon} \le \cbar n^{\log_b a - \varepsilon} \left( \frac{2b-1}{b-1} \right)^{\log_b a - \varepsilon} \sum_{i=0}^{k-1} b^{\varepsilon i} \\
 &amp; \le \cbar n^{\log_b a - \varepsilon} \left( \frac{2b-1}{b-1} \right)^{\log_b a - \varepsilon} \frac{n^\varepsilon - 1}{b^\varepsilon - 1} &lt; \frac{\cbar}{b^\varepsilon - 1} \left( \frac{2b-1}{b-1} \right)^{\log_b a - \varepsilon} n^{\log_b a} = O(n^{\log_b a})
\end{align*}
&#x4ECE;&#x800C;<script type="math/tex; ">T(n) = \Theta(n^{\log_b a}) + O(n^{\log_b a}) = \Theta(n^{\log_b a})</script>&#xFF0C;&#x5373;&#x6B64;&#x65F6;<script type="math/tex; ">T(n)</script>&#x7684;&#x590D;&#x6742;&#x5EA6;&#x7531;&#x524D;&#x4E00;&#x9879;&#x51B3;&#x5B9A;&#x3002;</p>
</li>
<li><p>&#x7531;<script type="math/tex; ">f(n) = \Theta (n^{\log_b a})</script>&#x53EF;&#x77E5;&#x5B58;&#x5728;&#x6B63;&#x5E38;&#x6570;<script type="math/tex; ">c_i</script>&#x3001;<script type="math/tex; ">d_i</script>&#x548C;<script type="math/tex; ">n_i</script>&#x4F7F;&#x5F97;&#x5BF9;<script type="math/tex; ">\forall n \ge n_i</script>&#x6709;
\begin{align*}
 a^i f(n_i) \le a^i c_i n_i^{\log_b a} &lt; a^i c_i \left( \frac{n}{b^i} \right)^{\log_b a} \left( 1 + \frac{b^i}{n} \frac{b}{b-1} \right)^{\log_b a} \le c_i \left( 1 + \frac{b}{b-1} \right)^{\log_b a} n^{\log_b a} = O(n^{\log_b a})
\end{align*}
&#x4EE5;&#x53CA;
\begin{align*}
 a^i f(n_i) \ge a^i d_i n_i^{\log_b a} \ge a^i d_i \left( \frac{n}{b^i} \right)^{\log_b a} = d_i n^{\log_b a} = \Omega (n^{\log_b a})
\end{align*}
&#x6545;<script type="math/tex; ">a^i f(n_i) = \Theta(n^{\log_b a})</script>&#xFF0C;&#x4E8E;&#x662F;
\begin{align*}
 g(n) = \sum_{i=0}^{k-1} a^i f(n_i) = \Theta(n^{\log_b a}) k = \Theta(n^{\log_b a} \lg n)
\end{align*}
&#x4ECE;&#x800C;<script type="math/tex; ">T(n) = \Theta(n^{\log_b a}) + \Theta(n^{\log_b a} \lg n) = \Theta(n^{\log_b a} \lg n)</script>&#xFF0C;&#x5373;&#x6B64;&#x65F6;<script type="math/tex; ">T(n)</script>&#x7684;&#x590D;&#x6742;&#x5EA6;&#x7531;&#x6C42;&#x548C;&#x8FD9;&#x4E00;&#x9879;&#x51B3;&#x5B9A;&#x3002;</p>
</li>
<li><p>&#x7531;&#x6761;&#x4EF6;&#x77E5;&#x5B58;&#x5728;<script type="math/tex; ">j</script>&#x4F7F;&#x5F97;&#x5F53;<script type="math/tex; ">n \ge n_{j-1}</script>&#x65F6;&#x9012;&#x63A8;&#x5F0F;<script type="math/tex; ">a f(\lceil n/b \rceil) \le c f(n)</script>&#x6052;&#x6210;&#x7ACB;&#xFF0C;&#x4E8E;&#x662F;
\begin{align*}
 a^j f(n_j) \le a^{j-1} c f(n_{j-1}) \le \cdots \le a^2 c^{j-2} f(n_2) \le a c^{j-1} f(n_1) \le c^j f(n_0)
\end{align*}
&#x4ECE;&#x800C;&#x5BF9;<script type="math/tex; ">\forall i \le j</script>&#x6709;<script type="math/tex; ">a^i f(n_i) \le c^{i} f(n)</script>&#xFF0C;&#x4EE3;&#x5165;&#x53EF;&#x5F97;
\begin{align*}
 g(n) &amp; = \sum_{i=0}^{k-1} a^i f(n_i) = \sum_{i=0}^j a^i f(n_i) + \overbrace{a^{j+1} f(n_{j+1}) + \cdots + a^{k-1} f(n_{k-1})}^{\text{&#x4E0D;&#x6EE1;&#x8DB3;&#x9012;&#x63A8;&#x5F0F;&#x7684;&#x90E8;&#x5206;&#xFF0C;&#x590D;&#x6742;&#x5EA6;&#x4E3A;}O(1)} \\
 &amp; \le \sum_{i=0}^j c^i f(n) + O(1) &lt; f(n) \sum_{i=0}^\infty c^i + O(1) = \frac{f(n)}{1-c} + O(1) = O(f(n))
\end{align*}
&#x53C8;<script type="math/tex; ">f(n)</script>&#x662F;<script type="math/tex; ">g(n)</script>&#x4E2D;&#x7684;&#x4E00;&#x9879;&#x4E14;<script type="math/tex; ">g(n)</script>&#x6240;&#x6709;&#x6C42;&#x548C;&#x9879;&#x975E;&#x8D1F;&#xFF0C;&#x6545;<script type="math/tex; ">g(n) \ge f(n)</script>&#xFF0C;&#x4ECE;&#x800C;
\begin{align*}
 g(n) = \Theta (f(n)) = \Omega(n^{\log_b a + \varepsilon}) &gt; \Theta(n^{\log_b a})
\end{align*}
&#x4E8E;&#x662F;<script type="math/tex; ">T(n) = \Theta(n^{\log_b a}) + g(n) = \Theta (f(n))</script>&#xFF0C;&#x5373;&#x6B64;&#x65F6;<script type="math/tex; ">T(n)</script>&#x7684;&#x590D;&#x6742;&#x5EA6;&#x7531;&#x6C42;&#x548C;&#x8FD9;&#x4E00;&#x9879;&#x51B3;&#x5B9A;&#x3002;</p>
</li>
</ol>
<hr>
<p>&#x3000;&#x3000;&#x6700;&#x540E;&#x8003;&#x8651;&#x5411;&#x4E0B;&#x53D6;&#x6574;&#xFF0C;&#x5373;
\begin{align*}
    n_i = \begin{cases}
        n &amp; i = 0 \\ \lfloor n_{i-1}/b \rfloor &amp; i &gt; 0
    \end{cases}
\end{align*}
&#x6839;&#x636E;<script type="math/tex; ">x-1 \le \lfloor x \rfloor \le x</script>&#x6613;&#x77E5;
\begin{align*}
    \frac{n}{b} - 1   \le n_1                               &amp; \le \frac{n}{b}   \\
    \frac{n}{b^2} - \frac{1}{b} - 1    \le n_2              &amp; \le \frac{n}{b^2} \\
    \frac{n}{b^3} - \frac{1}{b^2} - \frac{1}{b} - 1 \le n_3 &amp; \le \frac{n}{b^3} \\
    \vdots                                                  &amp;
\end{align*}
&#x4E8E;&#x662F;
\begin{align} \label{eq: ni-lower-bound}
    \frac{n}{b^i} - \frac{b}{b-1} = \frac{n}{b^i} - \frac{1}{1 - 1/b} &lt; \frac{n}{b^i} - \frac{1}{b^{i-1}} - \cdots - \frac{1}{b} - 1 \le n_i \le \frac{n}{b^i}
\end{align}
&#x4EE4;<script type="math/tex; ">k = \lfloor \log_b n(b-1) \rfloor - 2 \ge \log_b n(b-1) - 3</script>&#xFF0C;&#x5373;<script type="math/tex; ">n(b-1) \le b^{k+3}</script>&#xFF0C;&#x4EE3;&#x5165;&#x5F0F;(\ref{eq: ni-lower-bound})&#x53EF;&#x5F97;
\begin{align*}
    n_k \le \frac{n}{b^k} \le \frac{b^{k+3}}{b^k} = \frac{b^3}{b-1} = O(1)
\end{align*}
&#x6545;&#x9012;&#x63A8;&#x5230;&#x7B2C;<script type="math/tex; ">k</script>&#x8F6E;&#xFF0C;&#x5B50;&#x95EE;&#x9898;<script type="math/tex; ">T(n_k)</script>&#x5DF2;&#x7ECF;&#x662F;<script type="math/tex; ">O(1)</script>&#x590D;&#x6742;&#x5EA6;&#x4E86;&#xFF0C;&#x540C;&#x524D;&#x9762;&#x4E00;&#x6837;&#x6709;
\begin{align*}
    T(n) = a^k T(n_k) + f(n_0) + a f(n_1) + \cdots + a^{k-1} f(n_{k-1}) = \Theta(n^{\log_b a}) + \sum_{i=0}^{k-1} a^i f(n_i)
\end{align*}
&#x5173;&#x952E;&#x4F9D;&#x7136;&#x662F;&#x540E;&#x9762;&#x6C42;&#x548C;&#x8FD9;&#x4E00;&#x9879;&#xFF0C;&#x7EE7;&#x7EED;&#x5206;&#x60C5;&#x51B5;&#x8BA8;&#x8BBA;&#xFF1A;</p>
<ol>
<li><p>&#x7531;<script type="math/tex; ">f(n) = O(n^{\log_b a - \varepsilon})</script>&#x53EF;&#x77E5;&#x5B58;&#x5728;&#x6B63;&#x5E38;&#x6570;<script type="math/tex; ">c_i</script>&#x548C;<script type="math/tex; ">n_i</script>&#x4F7F;&#x5F97;&#x5BF9;<script type="math/tex; ">\forall n \ge n_i</script>&#x6709;
\begin{align*}
 a^i f(n_i) \le a^i c_i n_i^{\log_b a - \varepsilon} &lt; a^i c_i \left( \frac{n}{b^i} \right)^{\log_b a - \varepsilon} = c_i n^{\log_b a - \varepsilon} b^{\varepsilon i}
\end{align*}
&#x4EE4;<script type="math/tex; ">\cbar = \max_i \{c_i\}</script>&#x3001;<script type="math/tex; ">\nbar = \max_i \{n_i\}</script>&#xFF0C;&#x4E8E;&#x662F;&#x5BF9;<script type="math/tex; ">\forall n \ge \nbar</script>&#x6709;
\begin{align*}
 g(n) = \sum_{i=0}^{k-1} a^i f(n_i) &lt; \sum_{i=0}^{k-1} c_i n^{\log_b a - \varepsilon} b^{\varepsilon i} \le \cbar n^{\log_b a - \varepsilon} \sum_{i=0}^{k-1} b^{\varepsilon i} \le \cbar n^{\log_b a - \varepsilon} \frac{n^\varepsilon - 1}{b^\varepsilon - 1} = O(n^{\log_b a})
\end{align*}
&#x4ECE;&#x800C;<script type="math/tex; ">T(n) = \Theta(n^{\log_b a}) + O(n^{\log_b a}) = \Theta(n^{\log_b a})</script>&#xFF0C;&#x5373;&#x6B64;&#x65F6;<script type="math/tex; ">T(n)</script>&#x7684;&#x590D;&#x6742;&#x5EA6;&#x7531;&#x524D;&#x4E00;&#x9879;&#x51B3;&#x5B9A;&#x3002;</p>
</li>
<li><p>&#x7531;<script type="math/tex; ">f(n) = \Theta (n^{\log_b a})</script>&#x53EF;&#x77E5;&#x5B58;&#x5728;&#x6B63;&#x5E38;&#x6570;<script type="math/tex; ">c_i</script>&#x3001;<script type="math/tex; ">d_i</script>&#x548C;<script type="math/tex; ">n_i</script>&#x4F7F;&#x5F97;&#x5BF9;<script type="math/tex; ">\forall n \ge n_i</script>&#x6709;
\begin{align*}
 a^i f(n_i) \le a^i c_i n_i^{\log_b a} \le a^i c_i \left( \frac{n}{b^i} \right)^{\log_b a} \le c_i n^{\log_b a} = O(n^{\log_b a})
\end{align*}
&#x4EE5;&#x53CA;
\begin{align*}
 a^i f(n_i) &amp; \ge a^i d_i n_i^{\log_b a} \ge a^i d_i \left( \frac{n}{b^i} - \frac{b}{b-1} \right)^{\log_b a} = a^i d_i \left( \frac{n}{b^i} \right)^{\log_b a} \left( 1 - \frac{b^i}{n} \frac{b}{b-1} \right)^{\log_b a} \\
 &amp; = d_i n^{\log_b a} \left( 1 - \frac{b^i}{n} \frac{b}{b-1} \right)^{\log_b a}
\end{align*}
&#x6CE8;&#x610F;<script type="math/tex; ">k = \lfloor \log_b n(b-1) \rfloor - 2 \le \log_b n(b-1) - 2</script>&#xFF0C;&#x5373;<script type="math/tex; ">n(b-1) \ge b^{k+2}</script>&#xFF0C;&#x4E8E;&#x662F;
\begin{align*}
 1 &gt; 1 - \frac{b^i}{n} \frac{b}{b-1} \ge 1 - \frac{b^{i+1}}{b^{k+2}} &gt; 0 \Longrightarrow 1 - \frac{b^i}{n} \frac{b}{b-1} \in (0,1) \Longrightarrow a^i f(n_i) = \Omega (n^{\log_b a})
\end{align*}
&#x6545;<script type="math/tex; ">a^i f(n_i) = \Theta(n^{\log_b a})</script>&#xFF0C;&#x4E8E;&#x662F;
\begin{align*}
 g(n) = \sum_{i=0}^{k-1} a^i f(n_i) = \Theta(n^{\log_b a}) k = \Theta(n^{\log_b a} \lg n)
\end{align*}
&#x4ECE;&#x800C;<script type="math/tex; ">T(n) = \Theta(n^{\log_b a}) + \Theta(n^{\log_b a} \lg n) = \Theta(n^{\log_b a} \lg n)</script>&#xFF0C;&#x5373;&#x6B64;&#x65F6;<script type="math/tex; ">T(n)</script>&#x7684;&#x590D;&#x6742;&#x5EA6;&#x7531;&#x6C42;&#x548C;&#x8FD9;&#x4E00;&#x9879;&#x51B3;&#x5B9A;&#x3002;</p>
</li>
<li><p>&#x7531;&#x6761;&#x4EF6;&#x77E5;&#x5B58;&#x5728;<script type="math/tex; ">j</script>&#x4F7F;&#x5F97;&#x5F53;<script type="math/tex; ">n \ge n_{j-1}</script>&#x65F6;&#x9012;&#x63A8;&#x5F0F;<script type="math/tex; ">a f(\lfloor n/b \rfloor) \le c f(n)</script>&#x6052;&#x6210;&#x7ACB;&#xFF0C;&#x4E8E;&#x662F;
\begin{align*}
 a^j f(n_j) \le a^{j-1} c f(n_{j-1}) \le \cdots \le a^2 c^{j-2} f(n_2) \le a c^{j-1} f(n_1) \le c^j f(n_0)
\end{align*}
&#x4ECE;&#x800C;&#x5BF9;<script type="math/tex; ">\forall i \le j</script>&#x6709;<script type="math/tex; ">a^i f(n_i) \le c^{i} f(n)</script>&#xFF0C;&#x4EE3;&#x5165;&#x53EF;&#x5F97;
\begin{align*}
 g(n) &amp; = \sum_{i=0}^{k-1} a^i f(n_i) = \sum_{i=0}^j a^i f(n_i) + \overbrace{a^{j+1} f(n_{j+1}) + \cdots + a^{k-1} f(n_{k-1})}^{\text{&#x4E0D;&#x6EE1;&#x8DB3;&#x9012;&#x63A8;&#x5F0F;&#x7684;&#x90E8;&#x5206;&#xFF0C;&#x590D;&#x6742;&#x5EA6;&#x4E3A;}O(1)} \\
 &amp; \le \sum_{i=0}^j c^i f(n) + O(1) &lt; f(n) \sum_{i=0}^\infty c^i + O(1) = \frac{f(n)}{1-c} + O(1) = O(f(n))
\end{align*}
&#x53C8;<script type="math/tex; ">f(n)</script>&#x662F;<script type="math/tex; ">g(n)</script>&#x4E2D;&#x7684;&#x4E00;&#x9879;&#x4E14;<script type="math/tex; ">g(n)</script>&#x6240;&#x6709;&#x6C42;&#x548C;&#x9879;&#x975E;&#x8D1F;&#xFF0C;&#x6545;<script type="math/tex; ">g(n) \ge f(n)</script>&#xFF0C;&#x4ECE;&#x800C;
\begin{align*}
 g(n) = \Theta (f(n)) = \Omega (n^{\log_b a + \varepsilon}) &gt; \Theta(n^{\log_b a})
\end{align*}
&#x4E8E;&#x662F;<script type="math/tex; ">T(n) = \Theta(n^{\log_b a}) + g(n) = \Theta (f(n))</script>&#xFF0C;&#x5373;&#x6B64;&#x65F6;<script type="math/tex; ">T(n)</script>&#x7684;&#x590D;&#x6742;&#x5EA6;&#x7531;&#x6C42;&#x548C;&#x8FD9;&#x4E00;&#x9879;&#x51B3;&#x5B9A;&#x3002;</p>
</li>
</ol>
<footer class="page-footer"><span class="copyright">Copyright &#xA9; Avanti 2022 all right reserved&#xFF0C;powered by Gitbook</span><span class="footer-modification">&#x6587;&#x4EF6;&#x6700;&#x540E;&#x4FEE;&#x6539;&#x65F6;&#x95F4;&#xFF1A;
2022-03-11 01:23:50
</span></footer>
                                
                                </section>
                            
    </div>
    <div class="search-results">
        <div class="has-results">
            
            <h1 class="search-results-title"><span class='search-results-count'></span> results matching "<span class='search-query'></span>"</h1>
            <ul class="search-results-list"></ul>
            
        </div>
        <div class="no-results">
            
            <h1 class="search-results-title">No results matching "<span class='search-query'></span>"</h1>
            
        </div>
    </div>
</div>

                        </div>
                    </div>
                
            </div>

            
                
                <a href="Strassen.html" class="navigation navigation-prev navigation-unique" aria-label="Previous page: 矩阵乘法加速">
                    <i class="fa fa-angle-left"></i>
                </a>
                
                
            
        
    </div>

    <script>
        var gitbook = gitbook || [];
        gitbook.push(function() {
            gitbook.page.hasChanged({"page":{"title":"主定理证明","level":"1.3","depth":1,"previous":{"title":"矩阵乘法加速","level":"1.2","depth":1,"path":"posts/Strassen.md","ref":"posts/Strassen.md","articles":[]},"dir":"ltr"},"config":{"plugins":["mathjax@git+https://github.com/CHN-beta/plugin-mathjax.git#update_cdn","splitter","disqus","donate","github","github-buttons","copy-code-button","-lunr","-search","search-plus","advanced-emoji","emphasize","mermaid-gb3","puml","graph","chart","-sharing","sharing-plus","tbfed-pagefooter","anchors","terminal"],"root":".","styles":{"website":"styles/website.css"},"pluginsConfig":{"tbfed-pagefooter":{"copyright":"Copyright &copy Avanti 2022","modify_label":"文件最后修改时间：","modify_format":"YYYY-MM-DD HH:mm:ss"},"disqus":{"useIdentifier":false,"shortName":"algorithm-notes"},"emphasize":{},"github":{"url":"https://github.com/Avanti1980"},"puml":{},"splitter":{},"sharing-plus":{"qq":false,"all":["facebook","google","twitter","instapaper","linkedin","pocket","stumbleupon"],"douban":false,"facebook":true,"weibo":false,"instapaper":false,"whatsapp":false,"hatenaBookmark":false,"twitter":true,"messenger":false,"line":false,"vk":false,"pocket":true,"google":false,"viber":false,"stumbleupon":false,"qzone":false,"linkedin":false},"graph":{},"donate":{"alipay":"https://gitee.com/avanti1980/notes-on-math/raw/master/img/zfb.jpg","alipayText":"支付宝","button":"赏","title":"","wechat":"https://gitee.com/avanti1980/notes-on-math/raw/master/img/wx.jpg","wechatText":"微信"},"fontsettings":{"theme":"white","family":"sans","size":2},"highlight":{},"mermaid-gb3":{},"github-buttons":{},"mathjax":{"forceSVG":false,"version":"2.7.1"},"copy-code-button":{},"advanced-emoji":{"embedEmojis":false},"sharing":{"qq":true,"douban":true,"facebook":true,"weibo":true,"instapaper":false,"whatsapp":false,"hatenaBookmark":false,"twitter":true,"messenger":false,"line":true,"vk":false,"pocket":false,"google":true,"viber":false,"stumbleupon":false,"qzone":true,"linkedin":true},"terminal":{"copyButtons":true,"fade":false,"style":"flat"},"theme-default":{"styles":{"website":"styles/website.css","pdf":"styles/pdf.css","epub":"styles/epub.css","mobi":"styles/mobi.css","ebook":"styles/ebook.css","print":"styles/print.css"},"showLevel":false},"anchors":{},"chart":{"type":"c3"},"search-plus":{}},"theme":"default","author":"Avanti","pdf":{"pageNumbers":true,"fontSize":12,"fontFamily":"Arial","paperSize":"a4","chapterMark":"pagebreak","pageBreaksBefore":"/","margin":{"right":62,"left":62,"top":56,"bottom":56}},"structure":{"langs":"LANGS.md","readme":"README.md","glossary":"GLOSSARY.md","summary":"SUMMARY.md"},"variables":{},"title":"Algorithm Notes","language":"zh-hans","output.name":"site","gitbook":"3.2.3","description":"算法讲义"},"file":{"path":"posts/master-theorem.md","mtime":"2022-03-10T17:23:50.730Z","type":"markdown"},"gitbook":{"version":"3.2.3","time":"2022-03-10T17:23:54.764Z"},"basePath":"..","book":{"language":""}});
        });
    </script>
</div>

        
    
    <script src="../gitbook/gitbook.js"></script>
    <script src="../gitbook/theme.js"></script>
    
        
        <script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-mathjax/plugin.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-splitter/splitter.js"></script>
        
    
        
        <script src="https://cdnjs.cloudflare.com/ajax/libs/URI.js/1.16.1/URI.min.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-disqus/plugin.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-donate/plugin.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-github/plugin.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-github-buttons/plugin.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-copy-code-button/toggle.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-search-plus/jquery.mark.min.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-search-plus/search.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-mermaid-gb3/book/plugin.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-sharing-plus/buttons.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-terminal/plugin.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-fontsettings/fontsettings.js"></script>
        
    

    <script src="../gitbook/gitbook-plugin-mermaid-gb3/mermaid/mermaid.min.js"></script>

    </body>
</html>

